Coding \& Cryptography

• Paper 1, Section I, G

  Coding \& Cryptography

  Part II, 2017

  Let $C$ be a binary code of length $n$. Define the following decoding rules: (i) ideal observer, (ii) maximum likelihood, (iii) minimum distance.

  Let $p$ denote the probability that a digit is mistransmitted and suppose $p<1 / 2$. Prove that maximum likelihood and minimum distance decoding agree.

  Suppose codewords 000 and 111 are sent with probabilities $4 / 5$ and $1 / 5$ respectively with error probability $p=1 / 4$. If we receive 110 , how should it be decoded according to the three decoding rules above?

  comment

• Paper 2, Section $I$, G

  Coding \& Cryptography

  Part II, 2017

  Prove that a decipherable code with prescribed word lengths exists if and only if there is a prefix-free code with the same word lengths.

  comment

• Paper 3, Section I, G

  Coding \& Cryptography

  Part II, 2017

  Find and describe all binary cyclic codes of length 7 . Pair each code with its dual code. Justify your answer.

  comment

• Paper 4, Section I, G

  Coding \& Cryptography

  Part II, 2017

  Describe the RSA system with public key $(N, e)$ and private key $d$.

  Give a simple example of how the system is vulnerable to a homomorphism attack.

  Describe the El-Gamal signature scheme and explain how this can defeat a homomorphism attack.

  comment

• Paper 1, Section II, G

  Coding \& Cryptography

  Part II, 2017

  Let $C$ be a binary linear code. Explain what it means for $C$ to have length $n$ and $\operatorname{rank} k$. Explain what it means for a codeword of $C$ to have weight $j$.

  Suppose $C$ has length $n$, rank $k$, and $A_{j}$ codewords of weight $j$. The weight enumerator polynomial of $C$ is given by

  $$W_{C}(s, t)=\sum_{j=0}^{n} A_{j} s^{j} t^{n-j}$$

  What is $W_{C}(1,1) ?$ Prove that $W_{C}(s, t)=W_{C}(t, s)$ if and only if $W_{C}(1,0)=1$.

  Define the dual code $C^{\perp}$ of $C$.

  (i) Let $\mathbf{y} \in \mathbb{F}_{2}^{n}$. Show that

  $$\sum_{\mathbf{x} \in C}(-1)^{\mathbf{x} \cdot \mathbf{y}}= \begin{cases}2^{k}, & \text { if } \mathbf{y} \in C^{\perp} \\ 0, & \text { otherwise }\end{cases}$$

  (ii) Extend the definition of weight to give a weight $w(\mathbf{y})$ for $\mathbf{y} \in \mathbb{F}_{2}^{n}$. Suppose that for $t$ real and all $\mathbf{x} \in C$

  $$\sum_{\mathbf{y} \in \mathbb{F}_{2}^{n}} t^{w(\mathbf{y})}(-1)^{\mathbf{x} \cdot \mathbf{y}}=(1-t)^{w(\mathbf{x})}(1+t)^{n-w(\mathbf{x})}$$

  For $s$ real, by evaluating

  $$\sum_{\mathbf{x} \in C}\left(\sum_{\mathbf{y} \in \mathbb{F}_{2}^{n}}(-1)^{\mathbf{x} \cdot \mathbf{y}}\left(\frac{s}{t}\right)^{w(\mathbf{y})}\right)$$

  in two different ways, show that

  $$W_{C^{\perp}}(s, t)=2^{-k} W_{C}(t-s, t+s) .$$

  comment

• Paper 2, Section II, G

  Coding \& Cryptography

  Part II, 2017

  Define the entropy, $H(X)$, of a random variable $X$. State and prove Gibbs' inequality.

  Hence, or otherwise, show that $H\left(p_{1}, p_{2}, p_{3}\right) \leqslant H\left(p_{1}, 1-p_{1}\right)+\left(1-p_{1}\right)$ and determine when equality occurs.

  Show that the Discrete Memoryless Channel with channel matrix

  $$\left(\begin{array}{ccc} 1-\alpha-\beta & \alpha & \beta \\ \alpha & 1-\alpha-\beta & \beta \end{array}\right)$$

  has capacity $C=(1-\beta)(1-\log (1-\beta))+(1-\alpha-\beta) \log (1-\alpha-\beta)+\alpha \log \alpha$.

  comment

• Paper 4, Section I, H

  Coding \& Cryptography

  Part II, 2018

  What is a linear feedback shift register? Explain the Berlekamp-Massey method for recovering a feedback polynomial of a linear feedback shift register from its output. Illustrate the method in the case when we observe output

  $010111100010 \ldots$

  comment

• Paper 3, Section $I$, H

  Coding \& Cryptography

  Part II, 2018

  Compute the rank and minimum distance of the cyclic code with generator polynomial $g(X)=X^{3}+X^{2}+1$ and parity check polynomial $h(X)=X^{4}+X^{3}+X^{2}+1$. Now let $\alpha$ be a root of $g(X)$ in the field with 8 elements. We receive the word $r(X)=X^{2}+X+1$ $\left(\bmod X^{7}-1\right)$. Verify that $r(\alpha)=\alpha^{4}$, and hence decode $r(X)$ using minimum-distance decoding.

  comment

• Paper 2, Section $I$, H

  Coding \& Cryptography

  Part II, 2018

  What is the channel matrix of a binary symmetric channel with error probability $p$ ?

  State the maximum likelihood decoding rule and the minimum distance decoding rule. Prove that if $p<1 / 2$, then they agree.

  Let $C$ be the repetition code $\{000,111\}$. Suppose a codeword from $C$ is sent through a binary symmetric channel with error probability $p$. Show that, if the minimum distance decoding rule is used, then the probability of error is $3 p^{2}-2 p^{3}$.

  comment

• Paper 1, Section $\mathbf{I}$, H

  Coding \& Cryptography

  Part II, 2018

  State and prove Shannon's noiseless coding theorem. [You may use Gibbs' and Kraft's inequalities as long as they are clearly stated.]

  comment

• Paper 1, Section II, H

  Coding \& Cryptography

  Part II, 2018

  Define the bar product $C_{1} \mid C_{2}$ of binary linear codes $C_{1}$ and $C_{2}$, where $C_{2}$ is a subcode of $C_{1}$. Relate the rank and minimum distance of $C_{1} \mid C_{2}$ to those of $C_{1}$ and $C_{2}$ and justify your answer.

  What is a parity check matrix for a linear code? If $C_{1}$ has parity check matrix $P_{1}$ and $C_{2}$ has parity check matrix $P_{2}$, find a parity check matrix for $C_{1} \mid C_{2}$.

  Using the bar product construction, or otherwise, define the Reed-Muller code $R M(d, r)$ for $0 \leqslant r \leqslant d$. Compute the rank of $R M(d, r)$. Show that all but two codewords in $R M(d, 1)$ have the same weight. Given $d$, for which $r$ is it true that all elements of $R M(d, r)$ have even weight? Justify your answer.

  comment

• Paper 2, Section II, H

  Coding \& Cryptography

  Part II, 2018

  Describe the RSA encryption scheme with public key $(N, e)$ and private key $d$.

  Suppose $N=p q$ with $p$ and $q$ distinct odd primes and $1 \leqslant x \leqslant N$ with $x$ and $N$ coprime. Denote the order of $x$ in $\mathbb{F}_{p}^{*}$ by $\mathrm{O}_{p}(x)$. Further suppose $\Phi(N)$ divides $2^{a} b$ where $b$ is odd. If $\mathrm{O}_{p}\left(x^{b}\right) \neq \mathrm{O}_{q}\left(x^{b}\right)$ prove that there exists $0 \leqslant t<a$ such that the greatest common divisor of $x^{2^{t} b}-1$ and $N$ is a nontrivial factor of $N$. Further, prove that the number of $x$ satisfying $\mathrm{O}_{p}\left(x^{b}\right) \neq \mathrm{O}_{q}\left(x^{b}\right)$ is $\geqslant \Phi(N) / 2$.

  Hence, or otherwise, prove that finding the private key $d$ from the public key $(N, e)$ is essentially as difficult as factoring $N$.

  Suppose a message $m$ is sent using the $\mathrm{RSA}$ scheme with $e=43$ and $N=77$, and $c=5$ is the received text. What is $m$ ?

  An integer $m$ satisfying $1 \leqslant m \leqslant N-1$ is called a fixed point if it is encrypted to itself. Prove that if $m$ is a fixed point then so is $N-m$.

  comment